package com.lw.leetcode.arr.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 15. 三数之和
 * 剑指 Offer II 007. 数组中和为 0 的三个数
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/11 21:22
 */
public class ThreeSum {

    public static void main(String[] args) {
        ThreeSum test = new ThreeSum();

        // [[0, 0, 0]]
        int[] arr = {0, 0, 0};

        // [[-1, 0, 1]]
//        int[] arr = {-1, 0, 1};

        // [[-1, 0, 1]]
//        int[] arr = {1, -1, -1, 0};

        // [[-4,2,2],[-2,0,2]]
//        int[] arr = {2, 0, -2, -5, -5, -3, 2, -4};

        List<List<Integer>> lists = test.threeSum(arr);
        System.out.println(lists);
    }

    public List<List<Integer>> threeSum2(int[] nums) {
        int length = nums.length;
        List<List<Integer>> all = new ArrayList<>();
        if (length < 3) {
            return all;
        }
        Arrays.sort(nums);
        int f = nums[0];
        if (f > 0 || nums[length - 1] < 0) {
            return all;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int z = 0;
        int i = 0;
        int st = -1;
        int end = -1;
        for (; i < length; i++) {
            int num = nums[i];
            map.put(num, 1);
            if (num < 0) {
                st = i;
            } else if (num == 0) {
                z++;
            } else {
                if (end == -1) {
                    end = i;
                }
            }
        }
        if (end != -1 && st != -1) {
            int a1 = 0;
            int b1;
            for (int k = end; k < length; k++) {
                int a = nums[k];
                if (a == a1) {
                    continue;
                }
                if (z > 0 && map.containsKey(-a)) {
                    List<Integer> list = new ArrayList<>(3);
                    list.add(-a);
                    list.add(0);
                    list.add(a);
                    all.add(list);
                }
                a1 = a;
                b1 = 0;
                for (int j = k + 1; j < length; j++) {
                    int b = nums[j];
                    if (b == b1) {
                        continue;
                    }
                    b1 = b;
                    int c = -a - b;
                    if (map.containsKey(c)) {
                        List<Integer> list = new ArrayList<>(3);
                        list.add(c);
                        list.add(a);
                        list.add(b);
                        all.add(list);
                    }
                    if (c < f) {
                        break;
                    }
                }
            }
            a1 = 0;
            f = nums[end];
            for (int k = 0; k < st; k++) {
                int a = nums[k];
                if (a == a1) {
                    continue;
                }
                a1 = a;
                b1 = 0;
                for (int j = k + 1; j <= st; j++) {
                    int b = nums[j];
                    if (b == b1) {
                        continue;
                    }
                    b1 = b;
                    int c = -a - b;
                    if (map.containsKey(c)) {
                        List<Integer> list = new ArrayList<>(3);
                        list.add(c);
                        list.add(a);
                        list.add(b);
                        all.add(list);
                    }
                    if (c < f) {
                        break;
                    }
                }
            }
        }
        if (z > 2) {
            List<Integer> list = new ArrayList<>(3);
            list.add(0);
            list.add(0);
            list.add(0);
            all.add(list);
        }
        return all;
    }


    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        if (length < 3 || nums[0] > 0 || nums[length - 1] < 0) {
            return list;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.put(nums[i], i);
        }
        int st = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            int a = nums[i];
            if (a == st) {
                continue;
            }
            int sr = Integer.MIN_VALUE;
            for (int j = i + 1; j < length; j++) {
                int b = nums[j];
                if (sr == b || 0 - a - b < b) {
                    continue;
                }
                if (map.getOrDefault(0 - a - b, -1) > j) {
                    list.add(Arrays.asList(a, b, 0 - a - b));
                }
                sr = b;
            }
            st = a;
        }
        return list;
    }

}
